/FONT#0=NGR25/FONT#1=BDJ25/FONT#3=NGR30
␈↓␈↓↓␈↓β␈↓β
␈↓ ↓H
␈↓ ∧[COMPUTER SCIENCE DEPARTMENT
␈↓ ¬0STANFORD UNIVERSITY

␈↓ ↓H

␈↓ ↓H
␈↓ α)CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1973
␈↓ ¬eMIDTERM EXAM
␈↓␈↓ ¬JOpen Books and Notes

␈↓ ↓H

␈↓ ↓H
␈↓ α_Write␈α
LISP␈α
functions␈α
as␈α
follows␈α
using␈α
the␈α
M-expression␈α
notation␈α
used␈α
in␈α
class:

␈↓ α_1.␈α␈↓↓commontail[u,v]␈↓␈αis␈αthe␈αlongest␈αcommon␈αsublist␈αof␈α␈↓↓u␈↓␈αand␈αF1v␈↓␈αending␈αwith␈αthe␈αends␈αof␈αthe␈αlists.
␈↓ ↓HThus␈α
␈↓↓commontail[␈↓(A␈α
B␈α
C␈α
D␈α
E),(A␈α
C␈α
D␈α
E)]␈α
=␈α
(C␈α
D␈α
E).

␈↓ α_2.␈α
␈↓↓permut␈α
u␈↓␈α
is␈α
a␈α
list␈α
of␈α
all␈α
the␈α
permutations␈α
of␈α
the␈α
list␈α
␈↓↓u␈↓.␈α
Thus

␈↓ α_␈↓↓permut␈α
␈↓(A␈α
B␈α
C)␈α
=␈α
((A␈α
B␈α
C)(A␈α
C␈α
B)(B␈α
A␈α
C)(B␈α
C␈α
A)(C␈α
A␈α
B)(C␈α
B␈α
A)).

␈↓ ↓HThe␈α
order␈α
in␈α
which␈α
the␈α
permutations␈α
are␈α
listed␈α
is␈α
not␈α
important␈α
here.

␈↓ α_3.␈α∂Devise␈α∂a␈α∂list␈α∂structure␈α∂representation␈α∂of␈α∂positions␈α∂in␈α∂the␈α∞game␈α∞of␈α∞tic-tac-toe␈α∞(noughts␈α∞and
␈↓ ↓Hcrosses),␈αand␈αwrite␈αfunctions␈α␈↓↓ter␈αp␈↓,␈αwhich␈αtells␈αwhether␈αthe␈αgame␈αis␈αover␈αin␈αposition␈α␈↓↓p␈↓,␈α␈↓↓imval␈αp␈↓␈αwhich
␈↓ ↓Htells␈α∞the␈α∞value␈α∞of␈α∞the␈α∞game␈α∞for␈α∞a␈α∞terminated␈α∞position␈α∞(use␈α∞-1,␈α∞0␈α∞and␈α∞1␈α∞for␈α∞values),␈α
and␈α
␈↓↓successors␈α
p␈↓
␈↓ ↓Hwhich␈α∀gives␈α∀the␈α∀successors␈α∀to␈α∀a␈α∀non-terminating␈α∪position␈α∪␈↓↓p␈↓.␈α∪Make␈α∪no␈α∪special␈α∪effort␈α∪to␈α∪achieve
␈↓ ↓Hefficiency.